import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class Test {

    //验证栈序列
    public boolean validateStackSequences(int[] pushed,int[] poped){
        Stack<Integer> st = new Stack<>();
        int i = 0,n = poped.length;
        for (int x: pushed) {
            st.push(x);
            while(!st.isEmpty() && st.peek() == poped[i]){
                st.pop();
                i++;
            }
        }
        return i == n;
    }


    //字符串解码
    public String decodeString(String _s){
        Stack<StringBuffer> st = new Stack<>();
        st.push(new StringBuffer());//先放一个空串进去
        Stack<Integer> nums = new Stack<>();

        int i = 0, n = _s.length();
        char[]s = _s.toCharArray();

        while(i<n){
            if (s[i] >='0' && s[i] <='9'){
                int tmp =0;
                while(i<n && s[i] >='0' && s[i] <='9'){
                    tmp = tmp*10+(s[i]-'0');
                    i++;
                }
                nums.push(tmp);
            }else if(s[i] == '['){
                i++;
                StringBuffer tmp = new StringBuffer();
                while (i<n && s[i]>='a' && s[i] <='z'){
                    tmp.append(s[i]);
                    i++;
                }
                st.push(tmp);
            }else if(s[i] == ']'){
                StringBuffer tmp = st.pop();
                int k = nums.pop();
                while(k-- != 0){
                    st.peek().append(tmp);
                }
                i++;
            }else{
                StringBuffer tmp = new StringBuffer();
                while (i<n && s[i] >='a' && s[i] <='z'){
                    tmp.append(s[i]);
                    i++;
                }
                st.peek().append(tmp);
            }
        }
        return st.peek().toString();
    }





    //基本计算器II
    public int calculate(String _s){
        Deque<Integer> st = new ArrayDeque<>();
        char op = '+';
        int i = 0, n = _s.length();
        char[] s = _s.toCharArray();

        while(i<n){
            if (s[i] == ' ') i++;
            else if(s[i] >='0' && s[i] <='9'){
                int tmp = 0;
                while(i<n && s[i] >= '0' && s[i] <= '9'){
                    tmp = tmp*10 + (s[i] -'0');
                    i++;
                }
                if (op == '+') st.push(tmp);
                else if(op == '-') st.push(-tmp);
                else if (op == '*') st.push(st.pop()*tmp);
                else st.push(st.pop()/tmp);
            }else{
                op = s[i];
                i++;
            }
        }
        int ret = 0;
        while(!st.isEmpty()){
            ret+= st.pop();
        }
        return ret;
    }



    //比较含退格的字符串
    public boolean backspaceCompare(String s,String t){
        return changeStr(s).equals(changeStr(t));
    }
    public String changeStr(String s){
        StringBuffer ret = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch != '#') ret.append(ch);
            else{
                if (ret.length()>0) ret.deleteCharAt(ret.length()-1);
            }
        }
        return ret.toString();
    }



    //删除字符中的所有相邻重复项
    public String removeDuplicates(String _s){
        StringBuffer ret = new StringBuffer();

        char[] s = _s.toCharArray();
        for (char ch: s) {
            if (ret.length()>0 && ch == ret.charAt(ret.length()-1)){
                //出栈
                ret.deleteCharAt(ret.length()-1);
            }else{
                //进栈
                ret.append(ch);
            }
        }
        return ret.toString();
    }




}
